//输入一串数字（2-9），按九键字母表，得到所有的字母组合
#include <string>
using std::string;
const string letterMap[10]={
    "",//0
    "",//1  无意义
    "abc",//2
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz",//9
};
#include <vector>
using std::vector;
//这个和数字组合有点不同，后者是在一个序列里面选，而这个是每一个字母都从不同（也有重复但还是要假装换序列）的序列中选择
//如"23",要先从2再从3中选择，但无论是哪一种，都是一个for循环
//两者的for循环都是横向遍历序列
//但数字组合的回溯递归是继续遍历相同的序列，而电话字母类型是切换其他序列
string s;
vector<string> result;
                                        //Index指的是目前遍历的第几个数字（0开始）
void backtracking(const string& digits,int Index){
    if(Index==digits.size()) {  //超尾就代表已经满了
        result.push_back(s);
        return ;
    }

    int digit =digits[Index]-'0';   //digit指的是digits的第几个数字
    string letters=letterMap[digit];

    for(int i=0;i<letters.size();i++){  //for循环也是横向遍历序列的字母
        s.push_back(letters[i]);
        backtracking(digits,Index+1);      //回溯是向下一个数字进行选择
        
        s.pop_back();//回溯
    }
}
vector<string> letterCombinations(string digits) {
    if(!digits.size()) return result;
    backtracking(digits,0);
    return result;
}